/**
 * @author 张骏勇 张自豪 曹祯浩 李钜环
 * @brief 本文件实现的是一个linkedwGraph
 *  以下的类都为实体类，实现Gragh的方法
 *  存储方式：邻接数组s
*/

#ifndef LINKEDDWGRAPH
#define LINKEDDWGRAPH

#define NOT_FOUND -1
#define ERROR 0x3f3f3f3f
#define FOUND 1

#define maxSize 0x3f3f3f3f

#include "graph.h"


const int max_number = 100010;

template<class T>
class linkedwGraph : public Graph<T>{

    public:

    // 节点的数量
    int numberOfNode;

    // 边的数量
    int numberOfEdge;

    // 邻接数组用的
    vector<vector<Node<T>>> node_array;

    // 存点的主数组
    vector<NodeList> nodes_list;

    // 存边
    vector<Edge<T>> edge_list;

    // 用到的索引
    int idx = 0;

    private:

    // dfs函数内部递归实现
    bool rdfs(NodeList start, NodeList destination);

    // 根据两个字符串获取到节点的对象
    pair<int, int> find_node_list(string start, string destination);

    // 找到单独的点
    int find_single(string str);

    // 求解度
    int degree(int) const;

    // 求解出度
    int out_degree(int) const;

    // 求解入度
    int in_degree(int) const;

    public:

    // 构造函数
    linkedwGraph(int numberOfVertices);

    // 插入边的函数
    bool insertEdge(string start, string destination, T distance);

    // 插入点的函数
    void insertNode(string name);

    // 获取边的数量
    int getNumberOfEdge(){return numberOfEdge;}
    
    // 获取点的数量
    int getNumberOfNode(){return numberOfNode;}
    
    // 下面需要实现的是一些图的算法，返回值和参数列表可以修改，必要的时候可以修改类其中的属性，但是必须提前告知

    // 两个，一个dfs一个bfs，都实现一下吧

    // dfs算法实现
    int dfs_find(string start, string destination);

    // bfs算法实现
    int bfs_find(string start, string destination);

    // 拓扑序列实现
    void topo_find();

    // kruskal算法实现
    void kruskal();

    // prim算法实现
    void prim(string name, int visit[], int lowCost[]);

    // dijkstra算法实现
    void dijkstra(string start, string destination);


    // dijkstra算法实现（堆优化版本）
    void dijkstra_fast(string start, string destination);

    // 找到两个节点之间的最短距离 返回一个距离
    int find_min_function(Node<T> a, Node<T> b);

    // 找到两个节点之间的最短距离 返回一个路径名的字符串
    vector<string> find_min_path_function(Node<T> a, Node<T> b);
};




// 以下方法都在类的外边进行实现，这样阅读代码的人只需要阅读类的声明就知道方法的主要用途
// 所以我认为头文件尽量都写在外面会比较清晰




// 构造函数
template<class T>
linkedwGraph<T>::linkedwGraph(int numberOfVertices){
    while (1) 
	{
		if (numberOfVertices < 0) 
		{
			cout << "请重新输入：" << endl;
			cin >> numberOfVertices;
		}
		else 
		{
			break;
		}
	}
    numberOfEdge = 0;
    numberOfNode = 0;
}




// 插入边的函数，头插法
template<class T>
bool linkedwGraph<T>::insertEdge(string start, string destination, T distance){
    // 根据字符串找到节点a，b并且找到节点a，b所对应的node_list的索引位置
    NodeList a, b;

    int idx_a, idx_b;

    pair<int, int> temp = find_node_list(start, destination);

    idx_a = temp.first, idx_b = temp.second;

    a = this->nodes_list[idx_a], b = this->nodes_list[idx_b];

    if(idx_a == -1 || idx_b == -1) return false;
    
    a.outdegree ++;
    b.indegree ++;
    // 存一下边
    Edge<T>* edge_temp = new Edge<T>(idx_a, idx_b, distance);
    this->edge_list.push_back(*edge_temp);

    // 存一下点到node_array中
    Node<T>* a_ = new Node<T>(distance, idx_b);

    this->node_array[idx_a].push_back(*a_);
    return true;
}




// 插入点的函数
template<class T>
void linkedwGraph<T>::insertNode(string name){
    this->numberOfNode ++;
    vector<Node<T>> temp_Node;
    this->node_array.push_back(temp_Node);

    NodeList* temp_node_list = new NodeList(0, name);

    temp_node_list->idx = this->idx ++;

    this->nodes_list.push_back(*temp_node_list);
}



// dfs调用实现
template<class T>
int linkedwGraph<T>::dfs_find(string start, string destination){
    // 根据字符串找到节点a，b并且找到节点a，b所对应的node_list的索引位置
    NodeList a, b;

    int idx_a, idx_b;

    pair<int, int> temp = find_node_list(start, destination);

    idx_a = temp.first, idx_b = temp.second;

    a = this->nodes_list[idx_a], b = this->nodes_list[idx_b];

    if(idx_a == -1 || idx_b == -1) return ERROR;
    

    bool res = this->rdfs(a, b);

    if(!res) return NOT_FOUND;
    else return FOUND;
}



// rdfs内部实现
template<class T>
bool linkedwGraph<T>::rdfs(NodeList start, NodeList destination){
    if(start.info == destination.info){
        return true;
    }
    for(auto item = this->node_array[start.idx].begin();item != this->node_array[start.idx].end();item ++){
        int t = item->index;
        if(!this->nodes_list[t].st){  // 假如没有遍历过这个点的话
            this->nodes_list[t].st = true;
            rdfs(this->nodes_list[t], destination);
            this->nodes_list[t].st = false;
        }
    }
    return false;
}




//bfs的主体实现部分
template<class T>
int linkedwGraph<T>::bfs_find(string start, string destination){
    // 根据字符串找到节点a，b并且找到节点a，b所对应的node_list的索引位置
    NodeList a, b;
    int idx_a, idx_b;
    pair<int, int> temp = find_node_list(start, destination);
    idx_a = temp.first, idx_b = temp.second;
    a = this->nodes_list[idx_a], b = this->nodes_list[idx_b];
    if(idx_a == -1 || idx_b == -1) return ERROR;
    for(auto item : this->nodes_list){
        item.st = false;  //全部初始化一下
    }
    queue<NodeList> node_queue;
    node_queue.push(a);//先是第一个节点

    //存从开始到到达该点的距离
    int ans[1010];
    memset(ans, 0, sizeof ans);
    // 表示上一个节点
    NodeList last_node;
    // 下面就是bfs的模板了
    while(!node_queue.empty()){  // 一直遍历到队列为空
        // 每一次遍历中取出来队列中的第一个元素，并且将其弹出队头
        NodeList temp = node_queue.front();
        node_queue.pop();

        temp.st = true; // 将起点对应的st设置为true，表示已经被遍历过了

        if(temp.info == b.info){ // 假如找到了就直接打印出经过的数量
            cout << "到达 " << destination << " 经过最少地点的数量：" << ans[b.idx] + 2 << endl; //包括起点与终点
            return FOUND; // find
        }
        //遍历他的子节点
        for(auto item = this->node_array[temp.idx].begin();item != this->node_array[temp.idx].end();item++){
            if(!item->st){ // 假如这个点没有被遍历过的话
                int t = item->index;
                node_queue.push(this->nodes_list[t]); // 将子节点推送到队尾中
                item->st = true;
                if(temp.idx == a.idx) ans[item->index] = 1; // 第一个点特判一下
                else ans[item->index] = ans[last_node.idx] + 1; // 第二点之后就需要把前面的节点加一了
            }
        }
        last_node = temp;
    }
    return NOT_FOUND; // not found
}


// prim算法的实现部分
template <class T>
void linkedwGraph<T>::prim(string name, int visit[], int lowCost[])
{
    int n = this->numberOfNode;
    for (int i = 0; i < n; i++)
    {
        visit[i] = 0;
        lowCost[i] = maxSize;
    }
    int k = find_single(name);
    visit[k] = 1;
    for (LL i = 0; i < this->node_array[k].size(); i++)
    {
        int j=node_array[k][i].index;
        lowCost[j] = node_array[k][i].value;
    }

    while (true)
    {
        int index = 0;
        bool isOk = true;
        for (int i = 0; i < this->numberOfNode; i++)
        {
            if (visit[i] == 0)
            {
                isOk = false;
                index = i;
            }
        }
        if (isOk)
        {
            break;
        }

        for (int i = 0; i <this->numberOfNode; i++)
        {
            if (visit[i] == 0)
            {
                index = lowCost[index] < lowCost[i] ? index : i;
            }
        }
        //将其接入最小生成树中
        visit[index] = 1;

        //对lowcost[]进行更新
        for (LL i = 0; i < this->node_array[index].size(); i++)
        {
            int a = this->node_array[index][i].index;
            if (visit[a] == 0)
            {
                lowCost[a] = this->node_array[index][i].value < lowCost[a]
                    ? this->node_array[index][i].value : lowCost[a];
            }
        }
    }
    lowCost[k] = 0;
}


// 找到单个点的位置，返回一个索引值
template<class T>
int linkedwGraph<T>::find_single(string str)
{
    int idx_a = -1;
    int flag = 0;
    for (auto item = this->nodes_list.begin(); item != this->nodes_list.end(); item++) {
        if (item->info == str) {
            idx_a = flag;
        }
        flag++;
    }
    return idx_a;
}



//该函数找到start和destination的位置
template<class T>
pair<int, int> linkedwGraph<T>::find_node_list(string start, string destination) {
    int idx_a = -1, idx_b = -1;
    int flag = 0;
    for (auto item = this->nodes_list.begin(); item != this->nodes_list.end(); item++) {
        if (item->info == start) {
            idx_a = flag;
        }
        if (item->info == destination) {
            idx_b = flag;
        }
        flag++;
    }
    return { idx_a, idx_b };
}




// dijkstra算法的实现部分
template<class T>
void linkedwGraph<T>::dijkstra(string start, string destination){

    pair<int, int> node_idx = this->find_node_list(start, destination);

    int idx_a = node_idx.first, idx_b = node_idx.second;

    cout << "从 " << start << " 到 " << destination << " 的最短路径为：" << endl;

    bool st[max_number];
    T dist[max_number];

    // 初始化
    for(int i = 0;i < this->numberOfNode + 5;i++) st[i] = false;

    for(int i = 0;i < this->numberOfNode + 5;i++){
        dist[i] = INF;
    }
    
    dist[idx_a] = 0;

    for(int i = 0;i < this->numberOfNode - 1;i++){
        int t = -1;
        // 找到最小的边
        for(int j = 0;j < this->numberOfNode;j++){
            if(!st[j] && (t == -1 || dist[t] > dist[j])){
                t = j;
            }
        } 
        // 将这个点添加到集合中，并且剩下的所有点都要更新一遍
        for(int j = 0;j < this->numberOfNode;j++){
            vector<Node<T>> temp = this->node_array[t];
            T d = 0x3f3f3f3f;
            // 邻接数组中取出来距离
            for(LL k = 0;k < temp.size();k++){
                if(temp[k].index == j) d = temp[k].value;
            }
            // 更新
            dist[j] = min(dist[j], dist[t] + d);
        }

        st[t] = true;
        if(i) printf(" => ");
        cout << this->nodes_list[t].info;
        if(nodes_list[t].info == destination) break;
    }
    puts("");
    cout << "最短的距离为：" << dist[idx_b] << endl;
}




// dijkstra其实可以使用堆（优先队列进行优化，时间复杂度可以优化成O(nlog(n))）
template<class T>
void linkedwGraph<T>::dijkstra_fast(string start, string destination){
    // 定义st判断当前索引值的点是否遍历过
    // 并且将其全部初始化为false
    bool st[max_number];
    memset(st, false, sizeof st);

    cout << "从 " << start << " 到 " << destination << " 的最短路径为：" << endl;

    // 初始化一下距离数组
    T dist[max_number];
    memset(dist, 0x3f, sizeof dist);

    pair<T, int> temp = this->find_node_list(start, destination);
    int idx_a = temp.first, idx_b = temp.second;
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> heap;
    heap.push({0, idx_a});
    dist[idx_a] = 0;
    bool flag = false;

    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int index = t.second;
        // T distance = t.first;
        
        if(st[index]) continue;
        st[index] = true;

        for(auto i = this->node_array[index].begin();i != this->node_array[index].end();i ++){
            int j = i->index;
            T w = i->value;
            if(dist[j] > dist[index] + w){
                dist[j] = dist[index] + w;
                heap.push({dist[j], j});
            }
        }
        if(flag) {
            printf(" => ");
        }

        flag = true;
        cout << this->nodes_list[t.second].info;
        if(nodes_list[t.second].info == destination) break;
    }
    puts("");
    cout << "最短的距离为：" << dist[idx_b] << endl;
}


//寻找一个拓扑序列
template<class T>
void linkedwGraph<T>::topo_find(){
    // 这里我直接使用数组模拟队列
    int tt = -1, hh = 0;
    int q[max_number];
    // 记录入度的
    int d[max_number];
    // 初始化上面的数组
    memset(d, 0, sizeof d);
    for(int i = 0;i < this->numberOfNode;i++){
        for(LL j = 0;j < this->node_array[i].size();j++){
            int t = node_array[i][j].index;
            d[t] ++;
        }
    }
    // 将所有的入度为0的点入队
    for(int i = 0;i < this->numberOfNode;i++)
        if(!d[i])
            q[++ tt] = i;
    while(tt >= hh){
        // 每一次遍历弹出来对头的一个元素
        int t = q[hh ++];
        // 将这个点去掉，然后更新其子节点
        for(auto item = this->node_array[t].begin();item != this->node_array[t].end();item++){
            int t = item->index;
            d[t] --;
            // 如果为0直接push进去
            if(!d[t])
                q[++ tt] = t;
        }
    }
    // 最后打印输出答案
    if(tt != this->numberOfNode - 1) puts("当前图不存在拓扑序列");
    else{
        printf("存在拓扑序列，并且为：\n");
        for(int i = 0;i < this->numberOfNode;i++){
            if(i) printf("=>");
            cout << q[i] << ":" << this->nodes_list[q[i]].info;
        }
        puts("");
    }
}




template<class T>
void linkedwGraph<T>::kruskal()
{
    /*
    * mark数组用来判断当前各个顶点是否形成一个环
    * 互通的顶点的标记一样
    * 当选择一条边的时候必须保证这条边的两个顶点标记不同
    */
    int mark[this->numberOfNode];
    for (int i = 0; i < this->numberOfNode; i++)
        mark[i] = i;
    // 将数组按权值从小到大排序
    sort(this->edge_list.begin(), this->edge_list.end(), [](const Edge& e1, const Edge& e2) {e1.w < e2.w});
    int n;               // 当前已加入树的顶点，方便判断是否全部加入树
    int sum = 0;          // 权值之和
    vector<Edge<T>> vMinTree;
    for (int i = this->nodes_list[0].idx; i < this->numberOfNode; i++){
        //判断是否成环
        if (mark[this->edge_list[i].v1] != mark[this->edge_list[i].v2]){
            vMinTree.push_back(this->edge_list[i]);
            sum += this->edge_list[i].w;
            n++;
            // 修改mark数组，保证每个相连的边都修改成同一个值
            for (int j = 0; j < this->numberOfNode; j++)
            {
                if (mark[j] == mark[this->edge_list[i].v2])
                {
                    mark[j] = mark[this->edge_list[i].v1];
                }
            }
        }
        else continue;
        if (n == this->numberOfNode - 1) break;
    }
    //同上
    if (n == this->numberOfNode - 1)  
    {
        for (typename vector<Edge<T>>::iterator it = vMinTree.begin(); it != vMinTree.end(); it++)
        {
            cout << this->nodes_list[it->v1] << " "
                << this->nodes_list[it->v2] << " "
                << it->w << endl;
        }
        cout << "最短路径距离为：" << sum << endl;
    }
    else
    {
        cout << "查询不到最短路径" << endl;
    }
}



// 计算度
template<class T>
int linkedwGraph<T>::degree(int t) const{
    return out_degree(t) + in_degree(t);
}



template<class T>
int linkedwGraph<T>::out_degree(int t) const {
    return this->nodes_list[t].outdegree;
}



template<class T>
int linkedwGraph<T>::in_degree(int t) const {
    return this->nodes_list[t].indegree;
}



#endif